package com.java.ch033;

//栈
class Stack {
    long stackArray[];
    int size; //栈的大小
    int top; // 栈顶

    public Stack(int size) {
        this.size = size;
        this.stackArray = new long[size];
        this.top = -1;
    }

    //出栈
    public long pop() {
        return stackArray[top--];
    }

    //入栈
    public void push(long value) {
        stackArray[++top] = value;
    }

    //判断栈空
    public boolean isEmpty() {
        return top == -1;
    }

    //判断栈是否满
    public boolean isFull() {
        return top == size - 1;
    }

    //取栈顶元素
    public long peek() {
        return stackArray[top];
    }
}

//队列
class Queue {
    private long queueArray[];
    private int front; //队首
    private int rear;//队尾
    private int size;//队列大小
    private int count;//队列中元素个数

    public Queue(int size) {
        this.queueArray = new long[size];
        this.size = size;
        this.front = 0;
        this.rear = -1;
        this.count = 0;
    }

    public void insert(long value) { //插入
        if (rear == size - 1) rear = -1; //队列满
        queueArray[++rear] = value;
        count++;
    }

    public long remove() { //删除
        long temp = queueArray[front++];
        if (front == size) {
            front = 0;
        }
        count--;
        return temp;
    }

    public long peakFront() {//返回队列第一个元素
        return queueArray[front];
    }

    public boolean isEmpty() {//判空
        return count == 0;
    }

    public boolean isFull() {//判满
        return count == size;
    }

    public int Count() {//返回队列元素个数
        return count;
    }

    public void print() {//遍历队列元素
        for (int i = front; i < front + count; i++) {
            System.out.print(queueArray[i] + '\t');
        }
        System.out.println();
    }
}

class PriorityQueue {
    private int count;
    private long priorityArray[];
    private int size;

    public PriorityQueue(int size) {
        this.size = size;
        this.priorityArray = new long[size];
        this.count = 0;
    }

    public void insert(long value) {
        int i;
        if (count == 0)
            priorityArray[count++] = value;
        else {
            for (i = count - 1; i > 0; i--) {
                if (value < priorityArray[i]) {
                    priorityArray[i + 1] = priorityArray[i];
                } else
                    break;
            }
            priorityArray[i + 1] = value;
            count++;
        }
    }

    public long remove() {
        return priorityArray[--count];
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == size;
    }

    public void print() {
        for (int i = 0; i < count; i++) {
            System.out.print(priorityArray[i] + '\t');
        }
        System.out.println();
    }
}

//主函数
public class TextStackAndQueue {
    public static void main(String[] args) {
        System.out.println("1.数组实现顺序栈");
        Stack stack = new Stack(6);
        while (!stack.isFull()) {
            long r = (long) (Math.random() * 20);
            stack.push(r);
            System.out.println(r + '\t');
        }
        System.out.println();
        while (!stack.isEmpty()) {
            long value = stack.pop();
            System.out.print(value + '\t');
        }
        System.out.println();
        System.out.println("------------------------------------");
        System.out.println("2.数组实现顺序队列");
        Queue queue = new Queue(6);
        while (!queue.isFull()) {
            long value = (long) (Math.random() * 20);
            queue.insert(value);
        }
        queue.print();
        while (!queue.isEmpty()) {
            queue.remove();
            queue.print();
        }
        queue.print();
        System.out.println(queue.isEmpty());
        System.out.println("-----------------------------------------");
        System.out.println("3.数组实现优先队列");
        PriorityQueue priority = new PriorityQueue(6);
        while (!priority.isFull()) {
            long value = (long) (Math.random() * 20);
            priority.insert(value);
        }
        priority.print();
    }
}